# 详细注释见ShellSort.cpp
def ShellSort(a):
    increment = len(a)
    while increment >= 1:
        increment = increment // 3 + 1
        for i in range(increment, len(a), 1):
            if a[i] < a[i - increment]:
                temp = a[i]
                j = i - increment
                while j >= 0 and a[j] > temp:
                    # 记录后移
                    a[j + increment] = a[j]
                    j = j - increment
                a[j + increment] = temp
        if increment == 1:
            break

    print(a)


a = [4, 3, 99, 7, 7]
print(a)
ShellSort(a)
